In the field of Public Key Cryptography (PKC), Public-key Encryption with Keyword Search (PEKS) is known as a technique for performing a keyword search without decrypting encrypted data (see Non-Patent Literature 1).
This PEKS realizes, for example, an application as described below.
Assume a situation where a sender transmits a data file including confidential information to a receiver via an external database (to be referred to as a “server” hereinafter). That is, assume a situation where the sender uploads data files to the server, and the receiver downloads a necessary data file from the server by a keyword search.
It should be noted here that the sender and the receiver wish to share both data files and keywords without revealing them to the server.
The receiver prepares in advance a pair of a public key and a secret key of public-key encryption (to be used for encrypting and decrypting data files) and a pair of a public key and a secret key of PEKS (to be used for encrypting keywords and generating search queries). Then, the receiver publishes both of the public keys.
Using the public key of public-key encryption of the receiver, the sender encrypts a data file to generate a ciphertext of the data file. In addition, using the public key of PEKS, the sender encrypts a keyword to generate a ciphertext of the keyword. The ciphertext of the keyword generated using the public key of PEKS will be hereinafter referred to as an “encrypted tag”. The sender uploads the ciphertext of the data file together with the encrypted tag to the server.
Using the secret key of PEKS, the receiver encrypts a keyword to generate a ciphertext of the keyword. The ciphertext of the keyword generated using the secret key of PEKS will be hereinafter referred to as a “trapdoor”. The receiver sends this trapdoor to the server as a search query.
Using the received trapdoor, the server performs a secure search on each of encrypted tags of ciphertexts of all data files in a database. Then, the server transmits to the receiver a ciphertext of a data file which has been found as a hit in the secure search.
It has been a problem with PEKS that a search need to be performed on the entirety of data, so that search processing time increases in proportion to the number of data files.
To solve this problem, some methods have been proposed.
Patent Literature 1 discloses a method in which an index storage unit configured to store a keyword and a document name by associating them with each other and an encrypted database configured to store an encrypted document are provided, and a search is performed for a keyword in the index storage unit. If no hit is found in the search, then a search is performed on all documents in the encrypted database. The index storage unit is updated in accordance with a search result.
However, it is a problem with this method that a search needs to be performed on all documents until the index storage unit is updated properly, so that a search process cannot be made faster. It is also a problem with this method that if a large number of various types of search requests occur, the effect of the index storage unit is weakened, so that the search process cannot be made faster. Further, it is a problem with this method that an existing system of a PEKS scheme needs to be changed greatly.